\section{Diameter-based objective}
\label{sec:theory2}
In this section, we mention theoretical results for {\it Diameter-sTF} and {\it Diameter-mTF}. We show that these problems are NP-hard (note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work). We further present an algorithm {\it MinDiameter} (Algorithm ~\ref{algo:minDia})  which is an extension of {\it RarestFirst} in~\cite{LLT}, and prove that it achieves a 2-approximation factor (all proofs omitted for brevity).
%Note that the NP-hardness of {\it Diameter-sTF} does not follow from any previous work. However, due to space constraints the proofs are omitted in this draft.

\begin{algorithm}[]\label{algo:minDia}
\caption{MinDiameter(G, {\cal T})} 
\label{algo:minDia}
\begin{algorithmic}[1]
\FOR{each <$a, k$> $\in T$}
\STATE $S(a) = \{ i \mid a \in X_i \}$
\ENDFOR
\STATE $a_{rare} = \arg \min_{<a, k> \in T} |S(a)|$
\FOR{each $i \in S(a_{rare})$}
\FOR{each <$a, k$> $\in T$}
\STATE $R_{ia} = d_k(i, S(a), k)$
\ENDFOR
\STATE $R_i \leftarrow \max_a R_{ia}$
\ENDFOR
\STATE $i^* \leftarrow \arg \min R_i$
\STATE ${\cal X'} = \{ i^* \}$
\FOR{each <$a, k$> $\in T$}
\STATE ${\cal X'} = {\cal X'} \cup \{  Path_k(i^*, S(a), k) \}$
\ENDFOR
\end{algorithmic}
\end{algorithm}

\begin{claim} 
{\it Diameter-sTF} and {\it Diameter-mTF} problems are NP-complete.
\end{claim}

\begin{claim}
For any graph distance function $d$ that satisfies the triangle inequality, the algorithm {\it MinDiameter} achieves an approximation factor of $2$ for the {\it Diameter-sTF} and\\
{\it Diameter-mTF} problems.
\end{claim}


%The algorithm {\it MinDiameter} generalizes the algorithm {\it RarestFirst} described in ~\cite{LLT}. 
Algorithm {\it MinDiameter} is as follows. For each individual, say $i_r \in S(a_{rare})$ where $a_{rare}$ is the rarest skill (the skill with the minimum size support set $S$), and for each skill $a_i \in {\cal T}$, the algorithm finds the distance to all the nodes in the support set $S(a_i)$. Then, for each support set $S(a_i)$, it chooses the $k_i$-size subset of $S(a_i)$ such that the maximum shortest path distance between $i_r$ and the nodes in this subset is minimum among all $k_i$-size subsets of $S(a_i)$. We call this distance as $k_i$-th shortest distance between $i_r$ and $S(a_i)$ and denote it as $d_k(i_r, S(a_i), k_i)$. Further, we denote the set of $k_i$ shortest paths between $i_r$ and each of the nodes belonging to the corresponding $k_i$-size subset of $S(a_i)$ as $Path_k(i_r, S(a_i), k_i)$. Thus, for each $i_r \in S(a_{rare})$ the algorithm has identified $k_i$ nodes of skill $a_i$, thereby forming a possible solution team that satisfies the constraints. Finally, the algorithm then picks one of these solutions that has minimum diameter. 
%The algorithm is presented below in detail. 
The time complexity of the algorithm {\it MinDiameter}, assuming that all pairs shortest paths are pre-computed, is $O(n^2)$.

